/*
 * @Author: szx
 * @Date: 2022-05-22 15:06:12
 * @LastEditTime: 2022-05-22 15:16:53
 * @Description:
 * @FilePath: \leetcode\面试题\08\02\02.js
 */
/**
 * @param {number[][]} obstacleGrid
 * @return {number[][]}
 */
var pathWithObstacles = function (obstacleGrid) {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    if (obstacleGrid[0][0] == 1) return [];
    let res;
    const dfs = (i, j, path) => {
        if (res) return;
        if (obstacleGrid[i][j] == 1) return;
        path.push([i, j]);
        if (i == m - 1 && j == n - 1) {
            res = Array.from(path);
            return;
        }
        if (i + 1 < m) {
            dfs(i + 1, j, path);
        }
        if (j + 1 < n) {
            dfs(i, j + 1, path);
        }
        obstacleGrid[i][j] = 1;
        path.pop();
    };
    dfs(0, 0, []);
    return res ? res : [];
};
